/**
 * 给定一个整数数组 asteroids，表示在同一行的行星。
 *
 * 对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
 *
 * 找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
 *
 *
 *思路：单调栈
 * https://leetcode.cn/problems/asteroid-collision/
 */
class AsteroidCollision {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack=new LinkedList<>();
        int len=asteroids.length;
        if(len==0){
            return new int[0];
        }
        for(int i=0;i<len;i++){
            while(i<len&&!stack.isEmpty()&&stack.peekLast()>0&&asteroids[i]<0){
                int tmp1=Math.abs(stack.peekLast());
                int tmp2=Math.abs(asteroids[i]);
                if(tmp2>tmp1){
                    stack.pollLast();
                }else if(tmp2<tmp1){
                    i++;
                }else {
                    stack.pollLast();
                    i++;
                }
            }
            if(i<len)
            stack.offerLast(asteroids[i]);
        }
        int size=stack.size();
        int[] ret=new int[size];
        for(int i=0;i<size;i++){
            ret[i]=stack.pollFirst();
        }
        return ret;
    }
}